#include"Sort.h"

void InsertSort(int* arr, int n)//插入排序
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;	
		}
		arr[end + 1] = tmp;
	}
}

//gap越大 前面大数据越快到后面 后面小数据越快到前面 越不接近有序
//gap越小 越接近有序 gap==1 就是插入排序
void ShellSort(int* arr,int n)//希尔排序
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//保证最后一次gap一定是一
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
					break;
			}
			arr[end + gap] = tmp;
		}

	}
	
}

void Swap(int* px,int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

void SelectSort(int* arr, int n) //选择排序 时间复杂度O(N^2)
{
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		int mini, maxi;
		mini=maxi = start;//将第一个设置为最大最小
		for (int i = start + 1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
				mini = i;
			if (arr[i] > arr[maxi])
				maxi = i;
		}
		Swap(&arr[start], &arr[mini]);
		//如果start和maxi位置重叠 则需要修正maxi位置
		if (start == maxi)
			maxi = mini;
		Swap(&arr[end], &arr[maxi]);

		start++;
		end--;

	}
}

void AdjustDown(int* arr, int n, int root) //排升序 建大堆
{
	int parent = root;
	int child = parent * 2 + 1;
	if (arr[child] < arr[child + 1] && child + 1 < n)
		child++;
	while (child < n)
	{
		if (arr[parent] < arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;

	}

}

void HeapSort(int* arr, int n)
{
	for (int i = ((n - 1) - 1) / 2; i >= 0; i--)
		AdjustDown(arr,n,i);

	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
	
}

void BubbleSort(int* arr, int n)
{
	int end = n;
	while(end > 0)
	{
		for (int i = 1; i < end; i++)
		{
			if (arr[i - 1] > arr[i])
				Swap(&arr[i - 1], &arr[i]);

		}

	}
}

int GetMiddle(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
			return mid;
		else if (arr[left] > arr[right])
			return left;
		else
			return right;
	}
	else
	{
		if (arr[mid] > arr[right])
			return mid;
		else if (arr[left] < arr[right])
			return left;
		else
			return right;
	}

}

//双指针法
int PartSort1(int* arr, int left, int right)
{
	int midindex=GetMiddle(arr, left, right);
	Swap(&arr[midindex], arr[right]);
	int key = arr[right];//将一边设置为key 则从另一边先走
	int tmp=right;
	while (left < right)
	{
		while (left < right && arr[left] <= key)
			left++;
		while (left<right && arr[right]>=key)
			right--;
		Swap(&arr[left], &arr[right]);

	}
	Swap(&arr[left],&arr[tmp]);
	return left;
}
//挖坑法
int PartSort2(int* arr, int left, int right)
{
	//用key记录坑
	int key = arr[right];
	while (left < right)
	{
		//从left开始找到比key大的 填到right的坑里 left位置形成新的坑
		while (left < right && arr[left] <= key)
			left++;
		arr[right] = arr[left];
		//从right开始找到比key小的 填到left的坑里 right位置形成新的坑
		while (left < right && arr[right] >= key)
			right--;
		arr[left] = arr[right];
	}
	//将交点处坑填上
	arr[left] = key;
	return left;
}

//前后指针法
int PartSort3(int* arr, int left, int right)
{
	int pre = left - 1;
	int cur = left;
	int keyindex = right;
	while (cur < right)
	{
		if (arr[cur] < arr[keyindex] && ++pre != cur)//将小于key的放到pre左边
			Swap(&arr[cur], &arr[pre]);

		cur++;
	}
	pre++;
	Swap(&arr[pre], &arr[keyindex]);//以pre为分界 
	return pre;
}

//递归
void QuickSort1(int* arr, int left, int right)
{
	if (left < right)
	{
		int div = PartSort1(arr, left, right);
		// [left,div-1] div [div+1,right]
		QuickSort1(arr, left, div - 1);
		QuickSort1(arr,div+1,right);

	}

}
//非递归
//递归改非递归
//1.简单递归直接改成循环 
//2.用栈模拟存储数据
// 
//非递归优势:
//1.提高效率 递归建立函数栈帧有消耗 但对于现代计算机 优化效果微乎其微
//2.栈帧深度过深 会导致栈溢出 因为系统栈空间一般只有M级别
//数据结构栈模拟递归 数据存储在堆上 一般有G级别空间
void QuickSort2(int* arr, int left, int right)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);

	while (StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);

		int div = PartSort3(arr, begin, end);
		//[begin,div-1] div [div+1,end]

		if (div+1 < end)
		{
			StackPush(&st,end);
			StackPush(&st,div+1);
		}
		if (begin< div-1)
		{
			StackPush(&st, div-1);
			StackPush(&st, left);
		}

	}
	StackDestroy(&st);

}

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	//归并
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
			tmp[index++] = arr[begin1++];
		else
			tmp[index++] = arr[begin2++];
	}
	while (begin1 <= end1)
		tmp[index++] = arr[begin1++];
	while (begin2 <= end2)
		tmp[index++] = arr[begin2++];

	for (int i = left; i <= right; i++)
		arr[i] = tmp[i];


}


void MergeSort1(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

void MergeArray(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
{
	int left= begin1, right = end2;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
			tmp[index++] = arr[begin1++];
		else
			tmp[index++] = arr[begin2++];
	}
	while (begin1 <= end1)
		tmp[index++] = arr[begin1++];
	while (begin2 <= end2)
		tmp[index++] = arr[begin2++];

	for (int i = left; i <= right; i++)
		arr[i] = tmp[i];


}
//非递归
void MergeSort2(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	for (int gap = 1; gap <n; gap*=2)
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//若只有第一组 则不再需要合并直接break出去
			if (begin2 >= n)
				break;
			//若合并时第二组不全 则修边界
			if (end2 >= n)
				end2 = n - 1;
			MergeArray(arr, i, i + gap - 1, i + gap, i + 2 * gap - 1, tmp);
		}
			
	free(tmp);
}


void CountSort(int* arr, int n)
{
	int min = arr[0];
	int max = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (arr[i] < min)
			min = arr[i];
		if (arr[i] > max)
			max = arr[i];
	}
	int range = max - min;
	int* countarr = (int*)malloc(sizeof(int) * range);
	memset(countarr,0, sizeof(int) * range);

	//统计次数
	for (int i = 0; i < n; i++)
		countarr[arr[i]-min]++;
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (countarr[i--])
			arr[index++] = i + min;
	}
	free(countarr);
}